package dp;

public class _10_1049_最后一块石头的重量Ⅱ {
	// 思路：平分成两堆石头，求最接近其中一堆的方案(max)，
	// 再通过总数减去方案数，得到第二堆，第二堆再减去方案数，得到最小的可能重量
    public static int lastStoneWeightII(int[] stones) {
    	int sum = 0;
    	for(int i = 0; i < stones.length; i++) {
    		sum += stones[i];
    	}
    	// 拆分两堆石头
    	int mid = sum/2; // 第一堆石头
    	int dp[][] = new int[stones.length+1][mid+1];

    	// dp找到最接近第一堆石头总和的方案
    	for(int i = 1; i <= stones.length; i++) { // 物品
    		for(int j = 1; j <= mid; j++) { // 容积
    			if(stones[i-1] > j) { // 当前石头大小比容积大，则不使用该石头，使用上一次方案的值
    				dp[i][j] = dp[i-1][j];
    			}else {
    				dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-stones[i-1]] + stones[i-1]);
    			}
    		}
    	}
    	// 得出最接近第一堆石头的方案值后，总值减去方案值，就是另一堆石头的值
    	int other = sum - dp[stones.length][mid];
    	
    	// 将最第二堆石头值减去方案值，就是最小的可能重量
    	// 由于/2会自动向下取整，所以第二堆石头值要么大于第一堆，要么等于第一堆
    	return other - dp[stones.length][mid];
    }
    public static void main(String[] args) {
    	int stones[] = {31,26,33,21,40};
		System.out.println(lastStoneWeightII(stones));
	}
}
